package stu.day48;

public class Trie {

    class Treenode{

        int val;
        Treenode[] children = new Treenode[26];


    }

    Treenode root;

    public Trie() {
        root = new Treenode();
    }

    public void insert(String word) {
        Treenode node = root;
        for(char ch:word.toCharArray()){
            int num = ch-'a';
            if(node.children[num]==null){
                node.children[num]=new Treenode();
            }
            node = node.children[num];
        }
        node.val=1;
    }

    public boolean search(String word) {
        Treenode node = root;
        for (char ch:word.toCharArray()){
            int num = ch-'a';
            if(node.children[num]==null){
                return false;
            }
            node = node.children[num];
        }
        if(node.val==1){
            return true;
        }else {
            return false;
        }

    }

    public boolean startsWith(String prefix) {
        Treenode node = root;
        for (char ch:prefix.toCharArray()){
            int num = ch-'a';
            if(node.children[num]==null){
                return false;
            }
            node = node.children[num];
        }
        return true;


    }



}
